package cn.whdream.datastructure.linkedlist;

/**
 * 
 * @author Jack
 *  约瑟夫问题，环形链表
 */
public class JosepfuDemo {
	public static void main(String[] args) {
		CircleSingleLinkedList list = new CircleSingleLinkedList();
		list.add(5);
		list.show();
		list.count(1, 2);
 }
	
	/**
	 * 环形单链表
	 */
	private static class CircleSingleLinkedList{
		private Boy first = null;
		private int lastNum = 1;
		private Boy currentBoy = null;
		public void add(int num) {
			if (num < 1) {
				System.out.println("添加数字不得小于1");
			}
			
			int i = lastNum;
			lastNum += num;
			//因为每次lastNum都是下一次循环开始的第一个孩子的 no，所以当前循环遍历则是使用 -1的数字
			num = lastNum-1;
			for (; i <= num; i++) {
				//自己的写法
//				Boy lastBoy = currentBoy;
//				currentBoy = new Boy(i);
//				if (i == 1) {
//					first = currentBoy;
//				}else {
//					lastBoy.setNext(currentBoy);
//				}
//				if(i == num|| i == 1) {
//					currentBoy.setNext(first);
//				}
				
				//老师的写法
				//相当于boy每次都是最后一个节点
				Boy boy = new Boy(i);
				if(i == 1) {
					first = boy;
					first.setNext(first);
					currentBoy = first;
				}else {
					currentBoy.setNext(boy);
					boy.setNext(first);
					currentBoy = boy;
				}
			}
		}
		/**
		 * TODO 2019.07.29 约瑟夫问题需要研究一下，查询下
		 */
		public void count(int startNo,int count) {
			if (currentBoy == null) {
				throw new UnsupportedOperationException("请先添加数据");
			}
			if (first == null || startNo <1 || startNo > lastNum -1) {
				throw new IllegalArgumentException("输入的参数有误");
			}
			Boy helper = currentBoy;
			for (int i = 1; i < startNo; i++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			while (true) {
				if (helper == first) {
					break;
				}
				for(int j = 0;j < count-1;j++) {
					first = first.getNext();
					helper = helper.getNext();
				}
				System.out.println("小孩出圈："+first.getNo());
				first = first.getNext();
				helper.setNext(first);
			}
			System.out.println("最后留下了的小孩"+first);
		}
		
		
		public void show() {
			if (first == null) {
				System.out.println("环形链表为空");
			}else {
				Boy cuBoy = first;
				while (true) {
					System.out.println(cuBoy);
					if (cuBoy.next == first) {
						break;
					}
					cuBoy = cuBoy.next;
				}
			}
			System.out.println("lastNum:"+lastNum);
		}
	}
	/**
	 * 
	 * 小孩
	 */
	private static class Boy {
		int no;
		Boy next;
		public Boy(int no) {
			super();
			this.no = no;
		}
		
		public void setNext(Boy next) {
			this.next = next;
		}

		public int getNo() {
			return no;
		}
		
		public Boy getNext() {
			return next;
		}

		@Override
		public String toString() {
			return "Boy [no=" + no + "]";
		}
		
		
		
	}
}
